import { cbtPrint } from "hy-algokit";
import IHeap from "./IHeap";

class Heap<T> implements IHeap<T> {
  private _data: T[] = [];
  private _size: number = 0;
  private _isMaxHeap: boolean = true;

  constructor(arr: T[] = [], isMaxHeap: boolean = true) {
    this._isMaxHeap = isMaxHeap;
    if (arr.length > 0) {
      this.build_heap(arr);
    }
  }

  private compare(i: number, j: number): boolean {
    if (this._isMaxHeap) {
      return this._data[i] >= this._data[j];
    } else {
      return this._data[i] <= this._data[j];
    }
  }

  private swap(i: number, j: number): void {
    const temp = this._data[i];
    this._data[i] = this._data[j];
    this._data[j] = temp;
  }

  insert(value: T): void {
    this._data.push(value);
    this._size++;

    let index = this._size - 1;

    this.hearfy_up(index);
  }

  private hearfy_up(index: number): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(parentIndex, index)) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  extract(): T | undefined {
    if (this._size === 0) {
      return undefined;
    }
    if (this._size === 1) {
      this._size--;
      return this._data.pop() as T;
    }

    const topValue = this._data[0];
    this._data[0] = this._data.pop() as T;
    this._size--;

    this.hearfy_down(0);

    return topValue;
  }

  private hearfy_down(index: number = 0): void {
    let start = index;
    while (2 * start + 1 < this._size) {
      const childIndexLeft = start * 2 + 1;
      const childIndexRight = childIndexLeft + 1;
      let largerIndex = childIndexLeft;
      if (
        childIndexRight < this._size &&
        this.compare(childIndexRight, childIndexLeft)
      ) {
        largerIndex = childIndexRight;
      }

      if (this.compare(start, largerIndex)) {
        break;
      }

      this.swap(start, largerIndex);
      start = largerIndex;
    }
  }

  peek(): T | undefined {
    return this._data[0];
  }

  isEmpty(): boolean {
    return this._size === 0;
  }

  get length(): number {
    return this._size;
  }

  build_heap(array: T[]): void {
    this._data = array;
    this._size = array.length;
    const start = Math.floor((this._size - 1) / 2); // 从最后一个非叶子节点开始

    for (let i = start; i >= 0; i--) {
      this.hearfy_down(i);
    }
  }

  print(): void {
    console.log(this._data);
    cbtPrint(this._data);
  }
}

// const arr = [19, 100, 36, 17, 3, 25];
// const heap = new Heap<number>(arr, true);

// while (!heap.isEmpty()) {
//   console.log(heap.extract());
// }

// heap.print();

export default Heap;
